package sol.leetcode;

import java.util.Stack;

/**
 * Verify Preorder Serialization of a Binary Tree
 */
public class Issue331 {
    public boolean isValidSerialization(String preorder) {

        String[] symbols = preorder.split(",");
        Stack<String> stk = new Stack<String>();
        for (int i = 0; i < symbols.length - 1; ++i) {
            String symbol = symbols[i];
            if (symbol.equals("#")) {
                if (stk.empty()) return false;
                stk.pop();
            } else
                stk.push(symbol);
        }
        return stk.empty() && symbols[symbols.length - 1].equals("#");
    }

    public static void main(String[] args) {
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        //String preorder = "#,7,6,9,#,#,#";
        Issue331 sol = new Issue331();
        System.out.println(sol.isValidSerialization(preorder));
    }
}
